package leetcode_100;

/**
 *@author 周杨
 *UniqueBinarySearchTrees_96 给定一个整数n 输出所有平衡二叉树的数量 其中二叉树节点值为1到n
 *describe: 使用卡特兰数的思想 AC 100%
 *2018年5月19日 上午9:50:27
 */
public class UniqueBinarySearchTrees_96 {

	public static void main(String[] args) {
		UniqueBinarySearchTrees_96 test=new UniqueBinarySearchTrees_96();
		System.out.println(test.numTrees(3));

	}
	/**
	 * describe: 假设当前有N个节点 则有n种方法选取根  每种选完根 再有N-1种动归数量选取下一个根 
	 * 从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，
	 * 所以总的数量是将以所有结点为根的可行结果累加起来。
	 * 2018年5月19日 上午9:51:06
	 */
	public int numTrees(int n) {
       if(n<2)
    	   return n;
       int dp[]=new int[n+1];
       dp[0]=1;
       for(int i=1;i<=n;++i) {//给每个卡特兰数赋值
    	   for(int j=0;j<i;++j) {//每个卡特兰数需要n次相加
    		   dp[i]+=(dp[j]*dp[i-j-1]);
    	   }
       }
       return dp[n];
    }

}
